Programs, Programming Languages, Programming

Programs

A program is a sequence of instructions that specifies how to perform a computation.

Following instructions are fundamental:

• input: get data from the keyboard, a file, or some other device
• output: display data on the screen or send data to a file or an other device
• math: perform basic mathematical operations like addition and multiplication
• conditional execution: check for certain conditions and execute the appropriate sequence of instructions

These instructions correspond with the symbolic instructions provided by the instruction set of the computer, which we will call low-level language or assembly.

It is all that is needed to perform a general computation in the sense of Turing.

Programming Languages

We don't want to write a program in assembly:

• programming in assembly is tedious and errorprone (you need to know all the gory details...)
• assembly is not portable (you have to start over if you want to use a CPU with another instruction set)

i.e. we need a high-level programming language.

A high-level programming language introduces supplementary instructions:

• repetition: perform a sequence of instructions repeatedly, usually with some variation

Believe it or not, that's pretty much all there is to it. Every program you've ever used, no matter how complicated, is made of instructions that look more or less like these.

Programming and Algorithms

Programming is the process of breaking a large, complex task into smaller and smaller subtasks until the subtasks are simple enough to be performed with sequences of the basic instructions.

As we progress through this course, you will notice that although the particulars of the source code change from one problem area to the next, certain patterns will emerge in the approach we take.

An algorithm is a mechanical (no intelligence required) sequence of instructions for solving a specific problem, eg. Newton's method for root solving. Executing an algorithm is boring, but designing them is interesting, intellectual challenging, and a central part of this course.

From Source Code to Executable

The statements in a high-level programming language have to be translated to instructions that the CPU can execute. There are two ways to do this translation: interpreting or compiling.

An interpreter is a program that reads a high level program and does what it says, eg. a Jupyter notebook. In effect, it translates the program line-by-line, alternately reading lines and carrying out commands.

A compiler is a program that reads a high level program and translates it all at once, before executing any of the commands. Often you compile the program as a separate step, and then execute the compiled code later. In this case the high level program is called the source code and the translated program is called the object code or executable.

Historically compiled programs performed better, i.e. ran faster with less memory, than interpreted programs. Because the compilation step and the execution are decoupled, a compiler could work longer and generate better object code. The runtime overhead is also less. An interpreter allows to use runtime information during translation what makes it more flexible and easier to use. A command-line interface (or Jupyter notebook) allows to dynamically execute statements.

Nowadays with Just-In-Time (JIT) compilation we can use the flexibility of an interpreter with the performance of a compiler: the source code is compiled at runtime. We have however the overhead of both an interpreter and a compiler.

We will use 4 programming languages to illustrate the most important programming techniques:

• Matlab (Octave): uses a JIT compiler (experimental for Octave)
• Python: uses an interpreter
• Julia: uses a JIT compiler
• C++: (gcc, clang) uses a compiler or (cling for Jupyter notebook) a JIT compiler

The First Program

Traditionally, the first program you write in a new language is called Hello, World!.

Matlab (Octave):

disp('Hello, World!')

Python:

print('Hello, World!')

Julia:

println("Hello, World!")

C++:

#include <iostream>
int main () {
  std::cout << "Hello, World!" << std::endl; 
}

Debugging

Formal Language

A high-level language is a formal language, i.e. designed by people for a specific application, in our case to express computations.

Formal languages have strict rules about syntax, eg. $\mathrm{H_2O}$ is a syntactically correct chemical name, but $\mathrm{_2Zz}$ is not. Syntax refers to the structure of a program and the rules about that structure.

Syntax rules come in two flavors, pertaining to tokens and structure. Tokens are the basic elements of the language, such as words, numbers, parentheses, commas, and so on. In Python, a statement like

print('Happy New Year for ', 2018)

has 6 tokens: a function name, an open parenthesis, a string, a comma, a number, and a close parenthesis.

It is possible to make errors in the way one constructs tokens, eg.

'Happy New Year for

is not a legal string token.

It is also possible to make errors in the way the tokens are arranged, i.e. the structure of a statement; eg.

print)"Happy New Year for", 2018(

has an illegal structure.

When you read a sentence in a natural language or a statement in a formal language, you have to figure out what the structure of the sentence is. This process is called parsing.

Once you have parsed a sentence, you can figure out what it means, or the semantics of the sentence. Because we all grow up speaking natural languages, it is sometimes hard to adjust to formal languages. The meaning of a computer program is unambiguous and literal, and can be understood entirely by analysis of the tokens and structure.

Formal languages are more dense than natural languages, so it takes longer to read them. Also, the structure is important, so it is not always best to read from top to bottom, left to right. Instead, learn to parse the program in your head, identifying the tokens and interpreting the structure. Finally, the details matter. Small errors in spelling and punctuation, which you can get away with in natural languages, can make a big difference in a formal language.

Errors

Program is a complex process, and because it is done by humans, if often leads to errors. Programming errors are called bugs and the process of tracking them down and correcting them is called debugging.

Three kinds of errors can occur in a program: syntax errors, runtime errors, and semantic errors. It is useful to distinguish between them in order to track them down more quickly.

Syntax error

For example, parentheses have to come in matching pairs, so

(1 + 2)

is legal, but

8)

is a syntax error. If there is a syntax error anywhere in your program, a programming language displays an error message and quits, and you will not be able to run the program. During the first few weeks of your programming career, you might spend a lot of time tracking down syntax errors. As you gain experience, you will make fewer errors and find them faster.

Runtime error

The second type of error is a runtime error, so called because the error does not appear until after the program has started running. These errors are also called exceptions because they usually indicate that something exceptional (and bad) has happened.

Runtime errors are rare in the simple programs you will see in the first few lectures, so it might be a while before you encounter one.

Semantic error

The third type of error is semantic, which means related to meaning. If there is a semantic error in your program, it will run without generating error messages, but it will not do the right thing. It will do something else. Specifically, it will do what you told it to do.

Identifying semantic errors can be tricky because it requires you to work backward by looking at the output of the program and trying to figure out what it is doing.

The art of debugging

Programming, and especially debugging, sometimes brings out strong emotions. If you are struggling with a difficult bug, you might feel angry, despondent, or embarrassed.

Preparing for these reactions might help you deal with them. One approach is to think of the computer as an employee with certain strengths, like speed and precision, and particular weaknesses, like lack of empathy and inability to grasp the big picture.

Your job is to be a good manager: find ways to take advantage of the strengths and mitigate the weaknesses. And find ways to use your emotions to engage with the problem, without letting your reactions interfere with your ability to work effectively.

Learning to debug can be frustrating, but it is a valuable skill that is useful for many activities beyond programming.

Program Design

Top-down Design

Top-down design is the process of starting with a large task and breaking it down into smaller, more easily understandable pieces (subtask) that perform a portion of the desired task. Each subtask may in turn be subdivided into smaller subtasks if necessary. Once the program is divided into small pieces, each piece can be coded and tested independently. We do not attemmpt to combine the subtasks into a complete task until each of the subtasks has been verified to work properly by itself.

The concept of top-down design is the basis of our formal program design process.

Problem statement

Programs are usually written to fill some perceived need, but that need may not be articulated clearly by the person requesting the program.

Eg. a user may ask for a program to solve a system of linear equations. This request in not clear enough to allow a programmer to design a program to meet the need; he or she must first know much more about the problem to be solved. Is the system of equations real or complex? What is the maximum number of equations that the program must handle? Are there any symmetries in the equations that might be exploited to make the task easier? The program designer will have to talk with the user requesting the program, and the two of them will have to come up with a clear statement of exactly what they are trying to accomplish. A clear statement of the problem will prevent misunderstandings, and it will also help the program designer to properly organize his or her thoughts;

Design and write a program to solve a system of linear equations having real coefficients and with up to 20 equations in 20 unknowns.

Define inputs and outputs

The inputs to the program and the outputs produced by the program must be specified so that the new program will properly fit into the overall processing scheme.

In the example, the coefficients of the equations to be solved are probably in some pre-existing order, and our new program needs to be able to read thme in that order. Similarly, it needs to produce the answer required by the programs that may follow in thet overall processing scheme, and to write out those answers in the format needed by the programs following it.

Design the algorithm

Decomposition

An algorithm is a step-by-step procedure for finding the solution to a problem. The designer looks for logical divisions within the problem, and divides it up into subtasks along those lines. This process is called decomposition. If the subtasks are themselves large, the designer can break them up into even smaller subtasks. This process continues until the problem has been divided into many small pieces, each of which does a simple, clearly understandable job.

Stepwise refinement

After the problem has been decomposed into small pieces, each piece is further refined through a process called stepwise refinement. In this process, a designer starts with a general description of what the piece of code should do, and then defines in detail the procedure so that it is specific enough to be turned into high-level language statements. This is often done with flowcharts.

Convert into high-level language statements

If the decomposition and refinement process is carried out properly, this step will be very simple. All the programmer will have to do is to replace the flowchart elements with the corresponding high-level statements on a one-for-one basis.

Test, debug and document

This step is the real killer. The components of the program must first be tested individually, if possible, and then the program as a whole must be tested. When testing a program, we must verify that it works correctly for all legal input data sets. If the algorithm implemented in a program includes different branches, we must test all of the possible branches to confirm that the program operates correctly under every possible circumstance.

Unit testing

The first stage of testing is called unit testing. During unit testing, the individual subtasks of the program are tested separately to confirm that they work correctly. The programmer usually writes small programs called stubs to execute the code under test, and to see if the code is returning the proper results. This verifies the operation of the subtasks at a basic level before they are combined into larger groups.

Builds

After the unit testing is completed, the program goes through a series of builds during which the individual subtasks are combined to produce the final program. The first build of the program typically includes only a few of the subtasks. It is used to check the interactions among those subtasks and the functions performed by the combination of the subtasks. In successive builds, more and more subtasks are addedn until the entire program is complete. Testing is performed on each build, and any errors (bugs) that are detected are corrected before moving on to the next build.

Alpha release

The first complete version of the program is called the alpha release. It is exercised by the programmer in as many ways as possible, and the bugs discovered during the testing are corrected.

Beta release

When the most serious bugs have been removed from the program, a new version called the beta release is prepared. This release is normally given to users who have a need for the program. These users put the program through its paces under many different conditions and with many different input data sets, and they report any bugs that they find to the programmers. When those bugs have been corrected, the program is ready to be released for general use.

Documentation

Comments inside a program are intended to help you and others understand program design and how it is organised. Program comments occur in the midst of the program's source and temporarily interrupt the highly restricted syntax of a high-level programming language. Comments are entirely ignored by the interpreter or compiler and are allowed to enhance program clarity for humans.

Not only comments are include in the source but also Docstrings that describe to a user how to use the program (function):

• what the program (function) does
• all user options of the program (function)
• descriptions of what error messages mean

Structured Programming

As a part of the design process, it is necessary to describe the algorithm that you intend to implement. This description should be in a standard form that is easy for both you and other people to understand, and the description should aid you in turning your concept in high-level language statements.

The standard forms that we use to describe the algorithms are called constructs, and an algorithm described using these constructs is called a structured algorithm. When the algorithm is implemented in a high-level language, the resulting program is called a structured program.

Flowcharts

Flowcharts are a way to describe algorithms graphically. In a flowchart, different graphical symbols represent the different operations in the algorithm, and our standard constructs are made up of collections of one or more of these symbols.

Eg, the addition of 2 floating point values is described by the following pseudo-code:

1. Compare the exponents of the two numbers; shift fraction of the smaller one to the right until its exponent would match the larger exponent.

2. Add the fractions.

3. Normalize the sum, either shifting right and incrementing the exponent or shifting left and decrementing the exponent.

4. Check overflow or underflow? If yes, generate an exception.

5. Round the fraction to the appriorate number of bits.

6. Is the result still normalized? If yes, we are done; if no go to step 3.